#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N = 1e5 + 5, MAX = 0x7fffffff;

int n, m, s, dist[N];
vector<pair<int, int> >ph[N];

void dijkstr() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int> > > pg;
    fill(dist, dist + n + 1, MAX);
    dist[s] = 0;
    pg.push({0, s});
    while(!pg.empty()) {
        auto cur = pg.top();
        pg.pop();
        int d = cur.first, u = cur.second;
        if(d != dist[u])    continue;
        for(auto &e : ph[u]) {
            int v = e.first, w = e.second;
            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pg.push({dist[v], v});
            }
        }
    }
}

int main() {
    cin >> n >> m >> s;
    while(m--) {
        int u, v, w;
        cin >> u >> v >> w;
        ph[u].push_back({v, w});
    }
    dijkstr();
    for(int i=1; i<=n; i++)
        cout << dist[i] << " ";
    return 0;
} 